/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: syyyy
 * Date: 2025-10-16
 * Time: 20:40
 */
import java.util.PriorityQueue;
public class Solution {
    public static int minCompareTimes(int[] lengths) {
            // 边界情况处理
        if (lengths == null || lengths.length <= 1) {
            return 0;
        }

        // 使用优先队列（最小堆）存储序列长度，每次能快速获取最小的两个元素
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int len : lengths) {
            minHeap.add(len);
        }
        int total = 0; // 总比较次数
        // 不断合并两个最小的序列直到只剩一个序列
        while (minHeap.size() > 1) {
            // 取出两个最小的长度
            int a = minHeap.poll();
            int b = minHeap.poll();
            // 合并这两个序列需要比较次数为 a + b - 1
            int compare = a + b - 1;
            total += compare;
            // 将合并后的新序列长度加入堆中
            minHeap.add(a + b);
        }
        return total;
    }
    public static void main(String[] args) {
        // 测试案例
        int[] test1 = {3, 5, 2, 7};
        System.out.println("序列 [3,5,2,7] 的最少比较次数：" + minCompareTimes(test1)); // 预期结果：24

        int[] test2 = {1, 2, 3, 4, 5};
        System.out.println("序列 [1,2,3,4,5] 的最少比较次数：" + minCompareTimes(test2)); // 预期结果：32
    }
}


